It has long been known that when a message word in the form m=(m1, m2, . . . , mk) is to be sent over a noisy channel, recovery of the message at the receiving end of the channel can be enhanced by adding redundancy to the transmitted message. In one well-known approach, m is subjected, before transmission, to a linear transformation, thereby to produce a codeword c=(c1, c2, . . . , cn), in which the total number n of characters ci in the codeword is greater than the total number k of characters in the message word. The codeword, which incorporates desired redundant information, is transmitted over the channel and decoded at the receiving end.
Each character ci of the codeword is a weighted sum of characters of the corresponding message block. The respective weight coefficients can be expressed in the form of, for example, an n×k matrix. At the receiving end, the decoder uses the coding matrix, or equivalent information, in conjunction with well-known techniques to recover the transmitted message word.
Some examples of linear block codes are Reed-Solomon, BCH, Golay, Goppa, and Hamming codes.
One measure of the effectiveness of a linear code is the minimum code distance. Roughly speaking, the minimum code distance measures the amount of corruption a received codeword can sustain without being mistaken for a different codeword. In mathematical terms, the codewords of a given code are pictured as an array of points in an abstract mathematical space. Associated with the space is a measure of distance between pairs of points. One such distance measure is the well-known Hamming distance. With reference to such a space and such a distance measure, the minimum code distance is related to the separation between the closest pair of codewords.
Linear codes are typically characterized in terms of three values: the code length n, the message length k, and the minimum distance d. In linear codes of the prior art, however, it has not generally been possible to make independent selections of n, k, and d. For example, a primitive BCH code will be completely determined by the designed minimum distance d and the finite alphabet from which the message characters mi are to be selected. Since a Reed-Solomon code is a special case of a primitive BCH code, it will have the same property. (It should be noted that the message alphabet is often the binary alphabet {0, 1}.)
Thus, there has been a need for linear codes that can be designed with greater flexibility. There is a general requirement, known as the “singleton bound,”, that d can never be greater than n+k−1. However, given a message alphabet, there has been a need for codes that can be designed, within the constraint imposed by the singleton bound, with greater independence among the choices of n, k, and d.